package org.example.heterogeneous;

import lombok.Data;
import org.example.util.DisJointSet;

import java.util.*;

@Data
public class CoreCommunity {

    // 输入的边
    private List<Edge> edgeList;

    // 输入的顶点
    private List<Node> nodeList;

    // 邻接表
    private List<AdjacencyEdge> adjacencyEdgeList;

    private int[] first;

    // Gp图中的边
    private List<Edge> edgeListGp;

    // Gp图中的顶点
    private List<Node> nodeListGp;

    // Gp图中的邻接表
    private List<AdjacencyEdge> adjacencyEdgeListGp;

    // Gp图中每个顶点的core
    private int[] coreGp;

    private int[] firstGp;

    // 元路径
    private List<Integer> metaPath;

    // FastBCore算法中顶点的访问情况：即对每个顶点v来说，set中的元素u都是已经访问过的
    Map<Integer, Set<Integer>> visitedFastBCore;

    // 路径是否已经访问过
    Map<String, Boolean> pathExist;

    // 所有顶点的k个P路径实例
    Map<Integer, Map<Integer, String>> kPathInstance;

    public CoreCommunity(List<Edge> edgeList, List<Node> nodeList, List<AdjacencyEdge> adjacencyEdgeList, int[] first) {
        this.edgeList = edgeList;
        this.nodeList = nodeList;
        this.adjacencyEdgeList = adjacencyEdgeList;
        this.first = first;
    }

    public void HomBCore(List<Integer> path, String q, int targetType, int k) {
        // 元路径
        this.metaPath = path;
        Node targetNode = null;
        // 寻找目标类型的顶点集合
        List<Node> targetNodeList = new ArrayList<>();
        for (Node node : nodeList) {
            if (node.getType() == targetType) {
                targetNodeList.add(node);
                if (targetNode == null && q.equals(node.getContent())) {
                    targetNode = node;
                }
            }
        }
        // 未找到目标顶点
        if (targetNode == null) {
            System.out.println("未找到目标顶点q=" + q);
            return;
        }

        String str;
        // 标识边(x,y)是否已经存储
        Map<String, Boolean> edgeExist = new HashMap<>();

        edgeListGp = new ArrayList<>();
        List<Node> tempX;
        List<Node> tempY;
        int l = metaPath.size();
        for (Node node : targetNodeList) {
            tempX = new ArrayList<>();
            tempX.add(node);
            for (int i = 1; i < l; ++i) {
                tempY = new ArrayList<>();
                for (Node nodeX : tempX) {
                    for (int j = first[nodeX.getId()]; j != -1; j = adjacencyEdgeList.get(j).getNext()) {
                        int v = adjacencyEdgeList.get(j).getV();
                        Node neighborNode = nodeList.get(v);
                        if (neighborNode.getType().equals(metaPath.get(i))) {
                            tempY.add(neighborNode);
                        }
                    }
                }
                tempX = tempY;
            }
            // 将找到的顶点与顶点v建边
            int u = node.getId();
            int x, y, v;
            for (Node nodeX : tempX) {
                v = nodeX.getId();
                // 跳过自环
                if (u == v) {
                    continue;
                }
                x = Math.min(u, v);
                y = u ^ v ^ x;
                str = x + "-" + y;
                // 去除重边
                if (!edgeExist.containsKey(str)) {
                    edgeExist.put(str, true);
                    edgeListGp.add(new Edge(x, y));
                }
            }
        }
        // 根据图G中的边来重新定义图Gp中的顶点和边
        reCreatNodeAndEdge(edgeListGp);

        // core分解算法
        coreDecomposition();

//        System.out.println("图Gp中顶点的core为：");
//        for (int i = 0; i < nodeListGp.size(); ++i) {
//            System.out.println("core[" + i + "]=" + coreGp[i]);
//        }

        // 搜索包含q的k-core社区
        HomBCoreCommunitySearch(q, k);
    }


    public void FastBCore(List<Integer> path, String q, int k) {
        // 元路径
        this.metaPath = path;
        this.visitedFastBCore = new HashMap<>();
        this.pathExist = new HashMap<>();
        this.kPathInstance = new HashMap<>();

        Node targetNode = null;
        for (Node node : nodeList) {
            if (q.equals(node.getContent())) {
                targetNode = node;
                break;
            }
        }
        // 未找到目标顶点
        if (targetNode == null) {
            System.out.println("未找到目标顶点q=" + q);
            return;
        }

        List<Integer> tempX = new ArrayList<>();
        List<Integer> tempY;
        Set<Integer> tempS = new HashSet<>();
        tempX.add(targetNode.getId());
        tempS.add(targetNode.getId());
        int l = metaPath.size();
        Map<String, Integer> edgeLabel = new HashMap<>();

        // BSL方法
        while (!tempX.isEmpty()) {
            for (int i = 1; i < l; ++i) {
                tempY = new ArrayList<>();
                for (Integer nodeX : tempX) {
                    for (int j = first[nodeX]; j != -1; j = adjacencyEdgeList.get(j).getNext()) {
                        int v = adjacencyEdgeList.get(j).getV();
                        Node neighborNode = nodeList.get(v);
                        if (neighborNode.getType().equals(metaPath.get(i))) {
                            String edgeStr = Utils.getEdgeKey(nodeX, neighborNode.getId());
                            if (!edgeLabel.containsKey(edgeStr)) {
                                tempY.add(neighborNode.getId());
                                // 向这条边打上标签i
                                edgeLabel.put(edgeStr, i);
                            }
                        }
                    }
                }
                tempX = tempY;
            }
            // 将x中的元素添加到s中
            Iterator<Integer> iterator = tempX.iterator();
            while (iterator.hasNext()) {
                Integer nodeX = iterator.next();
                // 判断是否已经在集合s中
                // 如果已经在集合s中，则需将其从x中删除
                // 如果不在集合s中，则需将其加入s中
                if (tempS.contains(nodeX)) {
                    iterator.remove();
                } else {
                    tempS.add(nodeX);
                }
            }
        }

        Queue<Integer> tempQ = new LinkedList<>();
        for (Integer nodeS : tempS) {
            Map<Integer, String> nodeKPathInstance = findKPathInstance(nodeS, l, k);
            kPathInstance.put(nodeS, nodeKPathInstance);
            if (nodeKPathInstance.size() < k) {
                tempQ.add(nodeS);
            }
        }

        if(tempQ.contains(targetNode.getId())){
            System.out.println("没有找到包含q=" + q + "的连通k-core");
            return;
        }

        // DSL方法
        while (!tempQ.isEmpty()) {
            Integer v = tempQ.poll();
            tempS.remove(v);

            Map<Integer, String> nodeKPathInstanceV = kPathInstance.get(v);
            // 将φ(v)中的所有P连接顶点添加到U中
            List<Integer> tempU = new ArrayList<>(nodeKPathInstanceV.keySet());

            for (Integer nodeU : tempU) {
                Map<Integer, String> nodeKPathInstanceU = kPathInstance.get(nodeU);
                if (nodeKPathInstanceU == null)
                    continue;
                if (nodeKPathInstanceU.containsKey(v)) {
                    nodeKPathInstanceU.remove(v);

                    if (nodeKPathInstanceU.size() < k) {
                        // 寻找一个新路径
                        String newPath = findOnePathInstance(nodeU, l);
                        // 判断新路径是否存在
                        if ("".equals(newPath)) {
                            tempQ.offer(nodeU);
                        } else {
                            // 找到最后一个连接符的索引
                            int lastIndex = newPath.lastIndexOf("-");
                            if (lastIndex != -1) {
                                // 使用substring截取最后一部分数字
                                String lastPart = newPath.substring(lastIndex + 1);
                                Integer pp = Integer.parseInt(lastPart);
                                nodeKPathInstanceU.put(pp, newPath);
                            } else {
                                System.out.println("截取路径出错!!!");
                            }
                        }
                    }
                }
                // 将路径实例信息更新
                kPathInstance.put(nodeU, nodeKPathInstanceU);
            }
        }

        // 最后使用BSL方法寻找与q P-连通且在S中的顶点的最大集合
        tempX = new ArrayList<>();
        tempX.add(targetNode.getId());
        edgeLabel = new HashMap<>();
        Set<Integer> tempB = new HashSet<>();
        // 将目标顶点添加进去
        tempB.add(targetNode.getId());
        // BSL方法
        while (!tempX.isEmpty()) {
            for (int i = 1; i < l; ++i) {
                tempY = new ArrayList<>();
                for (Integer nodeX : tempX) {
                    for (int j = first[nodeX]; j != -1; j = adjacencyEdgeList.get(j).getNext()) {
                        int v = adjacencyEdgeList.get(j).getV();
                        Node neighborNode = nodeList.get(v);
                        if (neighborNode.getType().equals(metaPath.get(i))) {
                            String edgeStr = Utils.getEdgeKey(nodeX, neighborNode.getId());
                            if (!edgeLabel.containsKey(edgeStr)) {
                                tempY.add(neighborNode.getId());
                                // 向这条边打上标签i
                                edgeLabel.put(edgeStr, i);
                            }
                        }
                    }
                }
                tempX = tempY;
            }
            // 将x中的元素添加到B中
            Iterator<Integer> iterator = tempX.iterator();
            while (iterator.hasNext()) {
                Integer nodeX = iterator.next();

                // 判断是否已经在集合B中
                // 如果已经在集合B中，则需将其从x中删除
                // 如果不在集合B中，则需将其加入B中
                // 同时将所有目标类型的顶点都限制在S中
                if ((!tempS.contains(nodeX)) || tempB.contains(nodeX)) {
                    iterator.remove();
                } else {
                    tempB.add(nodeX);
                }

            }
        }

        if (tempB.size() > 1) {
            System.out.println("找到的包含q的连通k-core中的顶点如下：");
            for (Integer id : tempB) {
                System.out.println(nodeList.get(id));
            }
            System.out.println("共找到" + tempB.size() + "个顶点");

        } else {
            System.out.println("没有找到包含q=" + q + "的连通k-core");
        }


        // 将顶点信息展示出来，以便于比较
//        List<String> result = new ArrayList<>();
//        for (Integer id : tempB) {
//            result.add(nodeList.get(id).getContent());
//        }
//        result.sort(new Comparator<String>() {//使用List接口的方法排序
//            @Override
//            public int compare(String o1, String o2) {
//                return o1.compareTo(o2);
//            }
//        });
//        for (String str : result) {
//            System.out.println(str);
//        }


    }


    /**
     * core分解算法
     */
    public void coreDecomposition() {
        // 图Gp中的顶点数量
        int nodeNumber = nodeListGp.size();

        int[] degree = new int[nodeNumber + 1];
        boolean[] deleteFlag = new boolean[nodeNumber + 1];
        firstGp = new int[nodeNumber + 1];

//        System.out.println("图Gp中的边为：");
//        for (Edge edge : edgeListGp) {
//            System.out.println(edge);
//        }

        // 使用邻接表存储边
        // 同时计算每个顶点的度
        adjacencyEdgeListGp = Utils.addEdgeWithDegree(edgeListGp, nodeNumber, firstGp, degree);

        // 设置度
        for (int i = 0; i < nodeNumber; ++i) {
            Node node = nodeListGp.get(i);
            node.setDegree(degree[i]);
        }

//        System.out.println("Gp中的顶点（带degree）：");
//        nodeListGp.forEach(System.out::println);

        List<Node> nodesGp = new ArrayList<>(nodeListGp);

        // 排序
        Collections.sort(nodesGp);

        coreGp = new int[nodeNumber + 1];
        // core分解算法
        while (!nodesGp.isEmpty()) {
            // 得到最小度和顶点
            Node node = nodesGp.get(0);
//            System.out.println("要删除的最小度的顶点为" + node);
            int deg = node.getDegree();
            int v = node.getId();

            // 为该顶点赋值核心数
            coreGp[v] = deg;
            // 删除该顶点
            deleteFlag[v] = true;
            degree[v] = 0;

            // 更新剩余顶点的度
            updateNodeDegree(adjacencyEdgeListGp, v, deleteFlag, degree, firstGp);

            // flag标识剩余顶点中是否有度小于等于deg的顶点
            boolean flag = true;
            while (flag) {
                flag = false;
                // 删除剩余顶点中度小于等于deg的顶点
                for (int i = 1; i < nodesGp.size(); ++i) {
                    Node tmp = nodesGp.get(i);
                    if (!deleteFlag[tmp.getId()] && degree[tmp.getId()] <= deg) {
//                        System.out.println("受id=" + v + "顶点删除影响，下面将要删除的最小度的顶点为" + tmp);
                        flag = true;
                        deleteFlag[tmp.getId()] = true;
                        coreGp[tmp.getId()] = deg;
                        degree[tmp.getId()] = 0;
                        // 更新剩余顶点的度
                        updateNodeDegree(adjacencyEdgeListGp, tmp.getId(), deleteFlag, degree, firstGp);
                    }
                }
            }

            // 按照新的度重新排序
            nodesGp = new ArrayList<>();
            for (int i = 0; i < nodeNumber; ++i) {
                if (!deleteFlag[i]) {
                    nodesGp.add(nodeListGp.get(i));
                }
            }
            Collections.sort(nodesGp);
        }
    }

    /**
     * HomBCore方法，寻找包含q的连通k-core
     *
     * @param q
     * @param k
     */
    public void HomBCoreCommunitySearch(String q, int k) {
        // 图Gp中的顶点数量
        int nodeNumber = nodeListGp.size();

        DisJointSet disJointSet = new DisJointSet(nodeNumber);

        boolean[] flag = new boolean[nodeNumber + 1];
        for (Edge edge : edgeListGp) {
            int u = edge.getU();
            int v = edge.getV();
            if (coreGp[u] >= k && coreGp[v] >= k) {
                disJointSet.join(u, v);
                flag[u] = true;
                flag[v] = true;
            }
        }
        int[] pre = new int[nodeNumber + 1];

        int targetIndex = -1;
        // 更新每个节点的祖先节点
        for (int i = 0; i < nodeNumber; ++i) {
            if (q.equals(nodeListGp.get(i).getContent())) {
                targetIndex = i;
            }
            pre[i] = disJointSet.find(i);
        }
        if (targetIndex == -1) {
            System.out.println("在Gp图中未找到目标顶点q=" + q);
            return;
        }
        int targetPre = pre[targetIndex];
        List<Node> targetSet = new ArrayList<>();
        for (int i = 0; i < nodeNumber; ++i) {
            if (targetPre == pre[i]) {
                targetSet.add(nodeListGp.get(i));
            }
        }
        // targetSet最少也会包含targetNode，因此需要size>1
        if (targetSet.size() > 1) {
            System.out.println("找到的包含q的连通k-core中的顶点如下：");
            targetSet.forEach(System.out::println);
            System.out.println("共找到" + targetSet.size() + "个顶点");

        } else {
            System.out.println("没有找到包含q=" + q + "的连通k-core");
        }


        // 将顶点信息展示出来，以便于比较
//        List<String> result = new ArrayList<>();
//        for (Node node : targetSet) {
//            result.add(node.getContent());
//        }
//        result.sort(new Comparator<String>() {//使用List接口的方法排序
//            @Override
//            public int compare(String o1, String o2) {
//                return o1.compareTo(o2);
//            }
//        });
//        for (String str : result) {
//            System.out.println(str);
//        }

    }

    /**
     * 删除一个节点后，更新其相邻节点的度
     *
     * @param adjacencyEdges 邻接表
     * @param u              删除的节点
     * @param deleteFlag     该点是否已经被删除了
     * @param degree
     * @param first
     */
    public void updateNodeDegree(List<AdjacencyEdge> adjacencyEdges, int u, boolean[] deleteFlag, int[] degree, int[] first) {
        // 更新剩余顶点的度
        for (int i = first[u]; i != -1; i = adjacencyEdges.get(i).getNext()) {
            int v = adjacencyEdges.get(i).getV();
            if (!deleteFlag[v]) {
//                System.out.println("删除顶点" + u + "，导致顶点" + v + "的度减小");
                --degree[v];
            }
        }
    }

    /**
     * 根据图G中的边来重新定义图Gp中的顶点和边
     *
     * @param edges
     */
    public void reCreatNodeAndEdge(List<Edge> edges) {
//        System.out.println("未重新定义时图Gp中的边为：");
//        for (Edge edge : edgeListGp) {
//            System.out.println(edge);
//        }

        // 顶点是否已经存入图中
        Map<Integer, Integer> nodeInGraph = new HashMap<>();
        int u, v;
        nodeListGp = new ArrayList<>();
        int index = 0;
        Node node;
        int x, y;
        for (Edge edge : edges) {
            u = edge.getU();
            v = edge.getV();
            if (!nodeInGraph.containsKey(u)) {
                node = nodeList.get(u);
                x = index++;
                // 将在图G中的id改为在图Gp中的id
                node.setId(x);
                nodeListGp.add(node);
                nodeInGraph.put(u, x);
            } else {
                x = nodeInGraph.get(u);
            }
            if (!nodeInGraph.containsKey(v)) {
                node = nodeList.get(v);
                y = index++;
                // 将在G图中的id改为在Gp图中的id
                node.setId(y);
                nodeListGp.add(node);
                nodeInGraph.put(v, y);
            } else {
                y = nodeInGraph.get(v);
            }
            // 重新将顶点id设置为在图Gp中的id
            edge.setU(x);
            edge.setV(y);
        }

    }

    /**
     * 寻找k个P路径实例
     *
     * @param x
     * @param l
     * @param k
     * @return
     */
    public Map<Integer, String> findKPathInstance(Integer x, int l, int k) {
        Map<Integer, String> nodeKPathInstance;
        // 查询是否已搜索过路径
        if (kPathInstance.containsKey(x)) {
            nodeKPathInstance = kPathInstance.get(x);
        } else {
            nodeKPathInstance = new HashMap<>();
        }
        // 指定顶点的被访问过的顶点信息
        Set<Integer> nodeVisited;
        // 获取指定顶点的访问信息
        if (visitedFastBCore.containsKey(x)) {
            nodeVisited = visitedFastBCore.get(x);
        } else {
            nodeVisited = new HashSet<>();
        }
        // vis记录dfs过程中的访问信息，保证dfs不走回头路
        boolean[] vis = new boolean[nodeList.size()];
        vis[x] = true;
        // 深搜
        dfs(x, Integer.toString(x), 1, l, k, nodeVisited, nodeKPathInstance, vis);
        vis[x] = false;
        // 更新顶点x相关的被访问过的顶点信息
        visitedFastBCore.put(x, nodeVisited);
        return nodeKPathInstance;
    }

    /**
     * 深搜来寻找P路径实例
     *
     * @param x
     * @param path
     * @param i
     * @param l
     * @param k
     * @param nodeVisited
     * @param nodeKPathInstance
     */
    public void dfs(int x, String path, int i, int l, int k, Set<Integer> nodeVisited, Map<Integer, String> nodeKPathInstance, boolean[] vis) {
        if (nodeVisited.contains(x))
            return;
        if (nodeKPathInstance.size() == k) {
            return;
        }
        if (i == l) {
            if (!pathExist.containsKey(path)) {
                pathExist.put(path, true);
                nodeKPathInstance.put(x, path);
            }
            nodeVisited.add(x);
            return;
        }
        for (int j = first[x]; j != -1; j = adjacencyEdgeList.get(j).getNext()) {
            int v = adjacencyEdgeList.get(j).getV();
            if (vis[v])
                continue;
            Node neighborNode = nodeList.get(v);
            if (neighborNode.getType().equals(metaPath.get(i))) {
                vis[v] = true;
                dfs(v, path + "-" + v, i + 1, l, k, nodeVisited, nodeKPathInstance, vis);
                vis[v] = false;
            }
        }

        // 如果该节点的邻居节点都已经被访问过，则说明该节点也被完全访问
        int neighborNodeVisitedNumber = 0;
        int neighborNodeNumber = 0;
        for (int j = first[x]; j != -1; j = adjacencyEdgeList.get(j).getNext()) {
            ++neighborNodeNumber;
            int v = adjacencyEdgeList.get(j).getV();
            if (nodeVisited.contains(v)) {
                ++neighborNodeVisitedNumber;
            }
        }
        if (neighborNodeNumber == neighborNodeVisitedNumber) {
            nodeVisited.add(x);
        }

    }


    public String findOnePathInstance(Integer x, int l) {
        // 指定顶点的被访问过的顶点信息
        Set<Integer> nodeVisited = visitedFastBCore.get(x);

        boolean flag = false;
        String path = Integer.toString(x);
        // vis记录dfs过程中的访问信息，保证dfs不走回头路
        boolean[] vis = new boolean[nodeList.size()];
        vis[x] = true;
        // 深搜
        dfsOne(flag, x, path, 1, l, nodeVisited, vis);
        vis[x] = false;
        // 更新顶点x相关的被访问过的顶点信息
        visitedFastBCore.put(x, nodeVisited);
        if (!flag) {
            path = "";
        }
        return path;
    }

    public void dfsOne(boolean flag, int x, String path, int i, int l, Set<Integer> nodeVisited, boolean[] vis) {
        // flag标识是否已经找到了一个路径实例
        if (flag)
            return;
        if (nodeVisited.contains(x))
            return;
        if (i == l) {
            if (!pathExist.containsKey(path)) {
                pathExist.put(path, true);
                flag = true;
            }
            nodeVisited.add(x);
            return;
        }
        for (int j = first[x]; j != -1; j = adjacencyEdgeList.get(j).getNext()) {
            int v = adjacencyEdgeList.get(j).getV();
            if (vis[v])
                continue;
            Node neighborNode = nodeList.get(v);
            if (neighborNode.getType().equals(metaPath.get(i))) {
                vis[v] = true;
                dfsOne(flag, v, path + "-" + v, i + 1, l, nodeVisited, vis);
                vis[v] = false;
            }
        }

        // 如果该节点的邻居节点都已经被访问过，则说明该节点也被完全访问
        int neighborNodeVisitedNumber = 0;
        int neighborNodeNumber = 0;
        for (int j = first[x]; j != -1; j = adjacencyEdgeList.get(j).getNext()) {
            ++neighborNodeNumber;
            int v = adjacencyEdgeList.get(j).getV();
            if (nodeVisited.contains(v)) {
                ++neighborNodeVisitedNumber;
            }
        }
        if (neighborNodeNumber == neighborNodeVisitedNumber) {
            nodeVisited.add(x);
        }

    }

}
